package com.jason.java.lib.sort;

/**
 * Description:KuaiSuPaiXu
 *
 * @author 陈宝阳
 * @create 2020/9/15 19:53
 */
public class KuaiSuPaiXu {

  public static void main(String args[]) {
    int[] arr = { 10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19 };
    quickSort(arr, 0, arr.length - 1);
    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }

  }

  public static void quickSort(int[] a, int low, int high) {

    int i, j;
    if (low > high) {
      return;
    }
    int temp = a[low]; //设置基准数
    i = low;
    j = high;
    while (i < j) {
      //从右侧开始进行查找，找比当前基准数小的值
      while (i < j && temp <= a[j]) {
        //向左移动位置
        j--;
      }

      //从左侧开始进行查找，找比当前基准数大的值
      while (i < j && temp >= a[i]) {
        //向右移动位置
        i++;
      }

      //两个数字找到之后，进行判断是否满足交换的条件
      if (i < j) {

        int z = a[i];//左边找到的值缓存到z中
        int y = a[j];//右边找到的值缓存到y中

        //交换值
        a[i] = y;
        a[j] = z;
      }

      //交换完后，i<j，继续循环查找
    }

    //跳出循环 i = j,将基准为与i和j相等位置的数字交换
    a[low] = a[i];
    a[i] = temp;

    //递归调用左半数组
    quickSort(a, low, j - 1);
    //递归调用右半数组
    quickSort(a, j + 1, high);
  }

}
